
//打家劫舍
class Solution {
public:
    int rob(vector<int>& nums) 
    {
        if(nums.empty()) return 0;
        if(nums.size()==1) return nums[0];
        if(nums.size()==2) return max(nums[0],nums[1]);
        vector<int>dp(nums.size(),0);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++)
        {
        //(不考虑nums[i],只考虑nums[i]且不考虑之前,考虑nums[i]且考虑之前的)
            dp[i]=max(max(dp[i-1],nums[i]),dp[i-2]+nums[i]);
        }
        return dp[nums.size()-1];
    }
};
//旋转图像
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) 
    {
        // 以[a,b]  [c,d]为左上 右下顶点的矩阵 其翻转之后
        //依然在这个圈上
        //所以 实现一个函数 每次都可以解决一圈的旋转问题
        int a=0;
        int b=a;
        int c=matrix.size()-1;
        int d=c;
        while(a<c)
        {
            f(matrix,a,b,c,d);
            a++,b++;
            c--,d--;
        }
    }
    //传进来左上角和右下角的左边 翻转这两个点围城的矩形上的点
    void f(vector<vector<int>>&matrix,int a,int b,int c, int d)
    {
        // 1*1的矩阵 无须翻转
        // 2*2的矩阵 需要翻转一组
        // 3*3的矩阵需要翻转两组 比如 
        //第0组是 1 3 9 7
        //第1组是 2 6 8 4

        //第0组的第一个数 [a,b];
        //第1组的第一个数 [a,b+1]; 
        //第i组的第一个数  [a,b+i]

        //第0组的第二个数 [a,d]
        //第1组的第二个数 [a+1,d]
        //第i组的第二个数  [a+i,d]

        //第0组的第三个数 [c,d]
        //第1组的第三个数 [c,d-1];
        //第2组的第三个数 [c,d-2];
        //第i组的第三个数  [c,d-i];

        //第i组的第四个数为 [c-i,b]
        // i组的四个数分别为 [a,b+i]  [a+i,b] [c,d-i] [c-i,b]
        for(int i=0;i<c-a;i++)
        {
            int tmp=matrix[a][b+i];
            matrix[a][b+i]=matrix[c-i][b];
            matrix[c-i][b]=matrix[c][d-i];
            matrix[c][d-i]=matrix[a+i][d];
            matrix[a+i][d]=tmp;
        }
    }
};

//0 和 1 个数相同的子数组
class Solution {
public:
    int findMaxLength(vector<int>& nums) 
    {
        //先把0转为-1
        //思路 如果有两个前缀和都是同一个值 
        //则证明 这两个数之间是0和1个数相同的子数组
        // 0   1   2   3  4   
        // 1  (-1  -1  1  1) 
        // 
        map<int,int>mp;//(sum,出现的sum时的下标)
        mp[0]=-1;//目的是处理这种情况 -1 1 
        //mp中存放了{-1，0} 和 {0,1} 
        //显然已经出现了 和为0的子数组 但是由于mp中find(0)==mp.end()
        //导致res没有被更新
        int sum=0;
        int res=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i]==0?-1:1;
            if(mp.find(sum)!=mp.end())
            {
                res=max(res,i-mp[sum]);
            }
            else
            {
                mp[sum]=i;
            }
        }
         return res;
    }
};
